package com.masterlu.leetcode.daily.linkedlist.medium;

import com.masterlu.leetcode.daily.linkedlist.ListNode;

/**
 * 删除链表的倒数第 N 个结点
 * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 *
 * @Author：masterlu
 * @Date：2021/4/6 9:48 上午
 */
public class M19RemoveNthFromEnd {


    public ListNode removeNthFromEnd(ListNode head, int n) {

        //1.链表为空时直接返回
        if (head == null) {
            return head;
        }

        //2.统计链表长度，并使用尾部指针指向链表
        int size = 0;
        ListNode tail = head;
        while (tail.next != null) {
            size++;
            tail = tail.next;
        }

        //3.利用尾部指针查询指定元素。进行删除动作
        tail = head;
        ListNode curr = null;

        for (int i = 0; i < size - n + 1; i++) {
            tail = tail.next;
        }
        tail.next = tail.next.next;

        return head;
    }


    public ListNode answer(ListNode head, int n) {

        //1.链表为null，或者长度为1时，返回null
        if (head == null) {
            return head;
        }
        //2.循环统计链表长度
        int size = getLikedListSize(head);
        if (size == 1 && n == 1) {
            return null;
        }
        ListNode curr = head;
        //3.根据长度计算删除节点
        for (int i = 0; i < size - n; i++) {
            curr = curr.next;
        }
        curr.next = curr.next.next;
        return head;
    }

    private int getLikedListSize(ListNode head) {

        int size = 0;
        ListNode curr = head;
        while (curr.next != null) {
            size++;
            curr = curr.next;
        }


        return size;
    }
}
